{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第11章-条件随机场-拟牛顿法（附录B）\n",
    "&emsp;&emsp;拟牛顿法也是求解最优化问题的一个方法，针对牛顿法的缺陷提出来的新方法。  \n",
    "### 牛顿法\n",
    "&emsp;&emsp;对于一个无约束的最优化问题$$\\displaystyle \\mathop{\\min} \\limits_{x \\in \\text{R}^n} f(x)$$假设$f(x)$有二阶连续偏导数，使用迭代的方法求解最优解$x^*$，若第$k$步的迭代值为$x^{(k)}$，将$f(x)$在$x^{(k)}$进行二阶泰勒展开：$$f(x)\\doteq f(x^{(k)})+\\nabla f''(x^{(k)})(x-x^{(k)}) + \\frac{1}{2}(x-x^{(k)})^T H(x^{(k)})(x-x^{(k)})$$其中$H(x^{(k)})$是$f(x)$的海赛矩阵(Hesse matrix)$$H(x)=\\left[\\frac{\\partial^2 f}{\\partial x_i \\partial x_j} \\right]_{n \\times n}$$在这点$x^{(k)}$的值。 \n",
    "函数$f(x)$有极值，可计算$\\nabla f(x)=0$求极小值：  \n",
    "$\\nabla f(x) = \\nabla f''(x^{(k)})+ H_k(x-x^{(k)}) = 0$  \n",
    "$\\therefore x^{(k+1)} = x^{(k)} - H_k^{-1} \\nabla f(x^{(k)})$  \n",
    "**牛顿法基本思路：**  \n",
    "1. 在迭代的过程中，用一个二次函数逼近每一个迭代的点对应的函数值，如果函数有极小值，需要保证该函数是凸函数，对应于一维函数中，其二阶导数要大于0，对应于$n$维的情况，$H_k(x^{(k)})$是正定矩阵。  \n",
    "2. 在迭代的过程中需要计算$H_k^{-1}$，对于每一个$k$，$H_k$是不一样的，所以计算$H_k^{-1}$（$n \\times n$维矩阵）的计算量是非常大的，这就是牛顿法的一个缺陷。 \n",
    "3. 一般在用迭代的方式求解一个函数极值时，迭代基本的形式都是$x^{(k+1)}=x^{(k)}+\\lambda p_k$，在牛顿法中，更新步长$\\lambda=1$，更新方向$p_k=- H_k^{-1} \\nabla f(x^{(k)})$，如果保证是正定的，就可以保证这是一个向下的方向（可以达到收敛）  \n",
    "4. 除了牛顿法，在梯度下降法中，迭代形式是$x^{(k+1)}=x^{(k)}-\\lambda \\nabla f(x^{(k)})$，在$\\lambda$比较小时，可以保证使得$f(x)$下降的方向，只用到了$f(x)$在点$x^{(k)}$的一阶导，对应到多维中就是梯度。而在牛顿法中，用到了一阶导和二阶导，因为牛顿法用了二阶导，比梯度下降法更快，即能更快地找到$f(x)$取极小值对应的$x^*$。  \n",
    "\n",
    "### 拟牛顿法\n",
    "&emsp;&emsp;想有一个新方法：（1）同样借助了$f(x)$在点$x^k$的二阶导，所以比梯度下降法的收敛速度要更快；（2）寻找一个能代替$H_k^{-1}$的矩阵，使得求逆的过程更加便捷；拟牛顿法就具备上述两点。\n",
    "&emsp;&emsp;首先考察$H_k$矩阵，（1）该矩阵是正定的；（2）在牛顿法中，需要求解$\\nabla f(x^{k+1}) = \\nabla f''(x^{(k)})+ H_k(x-x^{(k)})$，当求解迭代$x^{(k+1)}$时，就是根据$f(x)$在点$x^{(k+1)}$的梯度等于0得到的求解公式。  \n",
    "令$\\delta_k=x-x^k,y_k=\\nabla f(x^{(k+1)}) - \\nabla f(x^{(k)})$  \n",
    "$\\therefore H_k \\delta_k=y_k$，希望替代矩阵也满足这个关系式。  \n",
    "可得到$H_k$的两个约束：$H_k \\delta_k=y_k, \\delta_k = H_k^{-1} y_k$称为拟牛顿条件。  \n",
    "&emsp;&emsp;但是不能直接用来求解$H_k$，因为$\\delta_k=x-x^k,y_k=\\nabla f(x^{(k+1)}) - \\nabla f(x^{(k)})$，首先求解$x^{(k+1)}$的值和对应的$\\nabla f(x^{(k+1)})$，这个替代矩阵就是为了计算$x^{(k+1)}$，所以这就是不能直接使用的一个拟牛顿条件，为了让这个条件可以使用，将$H_k$换成$H_{k+1}$，即$H_{k+1} \\delta_k=y_k, \\delta_k = H_{k+1}^{-1} y_k$，也就是说用$x^{(k+1)}$求解$H_{k+1}$，用$H_{k+1}$的替代求解$x^{(k+2)}$  \n",
    "\n",
    "### 书上对应的两个算法\n",
    "&emsp;&emsp;DFP算法用矩阵$G_k$代替$H_k^{-1}$，这个替代矩阵有一个递推的形式，这个关系是由$G_k$加上两个秩为1的矩阵构成的，假设$G_{k+1}=G_k+aVV^T+bUU^T$，寻找满足条件的$aV,bU$，就得到了书中DFP算法中给出的$G_k$递推公式：$$G_{k+1}=G_k+\\frac{\\delta_k \\delta_k^T}{\\delta_k^T y_k} - \\frac{G_k y_k y_k^T G_k}{y_k^T G_k y_k}$$从而找到了$H_{k+1}^{-1}$的替代。\n",
    "&emsp;&emsp;BFGS算法用矩阵$B_k$代替$H_k$，这个替代矩阵同样有一个递推的形式，这个关系同样是由$B_k$加上两个秩为1的矩阵构成的，书中给出了BFGS算法中的$B_k$递推公式：$$B_{k+1}=B_k+\\frac{y_k y_k^T}{y_k^T \\delta_k} - \\frac{B_k \\delta_k \\delta_k^T B_k}{\\delta_k^T B_k \\delta_k}$$&emsp;&emsp;其实还有一个问题： 在算法B.3中，依然要计算$B_k^{-1}$，为什么这个时候求解$B_k^{-1}$就可行，之前求解$H_k^{-1}$不可行呢？因为如果求出了$B_k^{-1}$，那么下一步$B_{k+1}^{-1}$和$B_k^{-1}$是满足一个函数关系式的，那么这个函数里面关于$B_k^{-1}$就不需要再计算了，这个关系式的推导见书上第223也的标注：\n",
    "> Sherman-Morrison公式：假设$A$是$n$阶可逆矩阵，$u,v$是$n$维向量，且$A+uv^T$也是可逆矩阵，则$$(A+uv^T)^{-1}=-\\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
